import java.util.*;

class Demo {
    	static int numD = 0;
	    static int numBin = 10;

    	public static void main(String[] args) {
		int[] data = new int[args.length - 1];
      	numD = Integer.parseInt(args[0]);
		for (int i = 0; i < args.length - 1; i++) {
			data[i] = Integer.parseInt(args[i+1]);
      	}
		System.out.println("Unsorted:");
      	for (int i = 0; i < data.length; i++) {
			System.out.println(data[i]);
      	}
		System.out.println("Sorted:");
		radixSort(data, numBin);
      	for (int i = 0; i < data.length; i++) {
			System.out.println(data[i]);
      	}
    	}

	public static int getDigit(int a, int k) {
		return Integer.parseInt(Integer.toString(a).substring(numD - k - 1, numD - k));
      }

	public static void radixSort(int[] A, int numBins) {
		ArrayList[] sourceBins = new ArrayList[numBins];
		ArrayList[] destBins = new ArrayList[numBins];

		for (int i = 0; i < numBins; i++) {
			sourceBins[i] = new ArrayList();
			destBins[i] = new ArrayList();
		}

		for (int i = 0; i < A.length; i++) {
			sourceBins[getDigit(A[i], 0)].add(A[i]);
		}

		for (int j = 0; j < numD; j++) {
			for (int i = 0; i < sourceBins.length; i++) {
				for (int k = 0; k < sourceBins[i].size(); k++) {
					destBins[getDigit(((Integer)sourceBins[i].get(k)).intValue(), j)].add(sourceBins[i].get(k));
				}
				sourceBins[i] = new ArrayList();
			}
			ArrayList[] tmp = sourceBins;
			sourceBins = destBins;
			destBins = tmp;
		}

		int i = 0;
		for (int j= 0; j < sourceBins.length; j++) {
			for (int k = 0; k < sourceBins[j].size(); k++) {
				A[i++] = ((Integer)sourceBins[j].get(k)).intValue();
			}
		}
	}
}